#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
// 最大子数组和：https://leetcode.cn/problems/maximum-subarray/description/
using namespace std;
class Solution {
public:
    //1.状态表示： dp[i]表示以nums[i]元素结尾的所有子数组中最大的一个
    //2.状态转移方程：dp[i]=max(nums[i],nums[i]+dp[i-1])
    //3.初始化： dp[0]=nums[0]
    //4.填表顺序：从左往右
    //5.返回值：max(dp[i])
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n+1,0);
        int ret=INT_MIN;
        for(int i=1;i<=n;i++) 
        {
            dp[i]=max(nums[i-1],dp[i-1]+nums[i-1]);
            ret=max(dp[i],ret);
        }
        return ret;  
    }
};